๐Ÿ‘ฉโ€๐Ÿ’ป 5014. ์Šคํƒ€ํŠธ ๋งํฌ

@Seongukbaek Posted February 21, 2022 ยท Updated February 21, 2022 ยท 4 min read

๋ฌธ์ œ

๊ฐ•ํ˜ธ๋Š” ์ฝ”๋”ฉ ๊ต์œก์„ ํ•˜๋Š” ์Šคํƒ€ํŠธ์—… ์Šคํƒ€ํŠธ๋งํฌ์— ์ง€์›ํ–ˆ๋‹ค. ์˜ค๋Š˜์€ ๊ฐ•ํ˜ธ์˜ ๋ฉด์ ‘๋‚ ์ด๋‹ค. ํ•˜์ง€๋งŒ, ๋Šฆ์ž ์„ ์ž” ๊ฐ•ํ˜ธ๋Š” ์Šคํƒ€ํŠธ๋งํฌ๊ฐ€ ์žˆ๋Š” ๊ฑด๋ฌผ์— ๋Šฆ๊ฒŒ ๋„์ฐฉํ•˜๊ณ  ๋ง์•˜๋‹ค.

์Šคํƒ€ํŠธ๋งํฌ๋Š” ์ด F์ธต์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ๊ณ ์ธต ๊ฑด๋ฌผ์— ์‚ฌ๋ฌด์‹ค์ด ์žˆ๊ณ , ์Šคํƒ€ํŠธ๋งํฌ๊ฐ€ ์žˆ๋Š” ๊ณณ์˜ ์œ„์น˜๋Š” G์ธต์ด๋‹ค. ๊ฐ•ํ˜ธ๊ฐ€ ์ง€๊ธˆ ์žˆ๋Š” ๊ณณ์€ S์ธต์ด๊ณ , ์ด์ œ ์—˜๋ฆฌ๋ฒ ์ดํ„ฐ๋ฅผ ํƒ€๊ณ  G์ธต์œผ๋กœ ์ด๋™ํ•˜๋ ค๊ณ  ํ•œ๋‹ค.

๋ณดํ†ต ์—˜๋ฆฌ๋ฒ ์ดํ„ฐ์—๋Š” ์–ด๋–ค ์ธต์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ๋ฒ„ํŠผ์ด ์žˆ์ง€๋งŒ, ๊ฐ•ํ˜ธ๊ฐ€ ํƒ„ ์—˜๋ฆฌ๋ฒ ์ดํ„ฐ๋Š” ๋ฒ„ํŠผ์ด 2๊ฐœ๋ฐ–์— ์—†๋‹ค. U๋ฒ„ํŠผ์€ ์œ„๋กœ U์ธต์„ ๊ฐ€๋Š” ๋ฒ„ํŠผ, D๋ฒ„ํŠผ์€ ์•„๋ž˜๋กœ D์ธต์„ ๊ฐ€๋Š” ๋ฒ„ํŠผ์ด๋‹ค. (๋งŒ์•ฝ, U์ธต ์œ„, ๋˜๋Š” D์ธต ์•„๋ž˜์— ํ•ด๋‹นํ•˜๋Š” ์ธต์ด ์—†์„ ๋•Œ๋Š”, ์—˜๋ฆฌ๋ฒ ์ดํ„ฐ๋Š” ์›€์ง์ด์ง€ ์•Š๋Š”๋‹ค)

๊ฐ•ํ˜ธ๊ฐ€ G์ธต์— ๋„์ฐฉํ•˜๋ ค๋ฉด, ๋ฒ„ํŠผ์„ ์ ์–ด๋„ ๋ช‡ ๋ฒˆ ๋ˆŒ๋Ÿฌ์•ผ ํ•˜๋Š”์ง€ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๋งŒ์•ฝ, ์—˜๋ฆฌ๋ฒ ์ดํ„ฐ๋ฅผ ์ด์šฉํ•ด์„œ G์ธต์— ๊ฐˆ ์ˆ˜ ์—†๋‹ค๋ฉด, "use the stairs"๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

์ž…๋ ฅ

  • ์ฒซ์งธ ์ค„์— F, S, G, U, D๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค S, G โ‰ค F โ‰ค 1000000, 0 โ‰ค U, D โ‰ค 1000000) ๊ฑด๋ฌผ์€ 1์ธต๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜๊ณ , ๊ฐ€์žฅ ๋†’์€ ์ธต์€ F์ธต์ด๋‹ค.

์ถœ๋ ฅ

  • ์ฒซ์งธ ์ค„์— ๊ฐ•ํ˜ธ๊ฐ€ S์ธต์—์„œ G์ธต์œผ๋กœ ๊ฐ€๊ธฐ ์œ„ํ•ด ๋ˆŒ๋Ÿฌ์•ผ ํ•˜๋Š” ๋ฒ„ํŠผ์˜ ์ˆ˜์˜ ์ตœ์†Ÿ๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค. ๋งŒ์•ฝ, ์—˜๋ฆฌ๋ฒ ์ดํ„ฐ๋กœ ์ด๋™ํ•  ์ˆ˜ ์—†์„ ๋•Œ๋Š” "use the stairs"๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

๐Ÿ“ Logic

class Pair { int floor; int cnt; public Pair(int floor, int cnt) { this.floor = floor; this.cnt = cnt; } }
  • ์ธต ์ •๋ณด์™€ ๋ฒ„ํŠผ ๋ˆ„๋ฅธ ํšŸ์ˆ˜๋ฅผ ์ €์žฅํ•˜๊ธฐ ์œ„ํ•ด Pair class๋ฅผ ์ƒ์„ฑํ–ˆ๋‹ค.
Queue<Pair> q = new LinkedList<>(); q.add(new Pair(S, 0)); visited[S] = true; while(!q.isEmpty()) { Pair now = q.poll(); int now_floor = now.floor; int now_cnt = now.cnt; if (now_floor == G) { System.out.println(now_cnt); return; } for (int go : upDown) { int nxFloor = now_floor + go; if (nxFloor <= 0 || nxFloor > F) continue; if (visited[nxFloor]) continue; q.add(new Pair(nxFloor, now_cnt + 1)); visited[nxFloor] = true; } }
  • ํ˜„์žฌ ์ธต์—์„œ ๋ชฉํ‘œ ์ธต๊นŒ์ง€ ๊ฐ€๊ธฐ ์œ„ํ•ด BFS๋กœ ์ด๋™ ๊ฐ€๋Šฅํ•œ ์ธต๊ณผ ๋ฒ„ํŠผ ๋ˆ„๋ฅธ ํšŸ์ˆ˜๋ฅผ Queue ์— ์ €์žฅํ•œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; class Pair { int floor; int cnt; public Pair(int floor, int cnt) { this.floor = floor; this.cnt = cnt; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] line = br.readLine().split(" "); int F = Integer.parseInt(line[0]), S = Integer.parseInt(line[1]), G = Integer.parseInt(line[2]); int[] upDown = {Integer.parseInt(line[3]), -Integer.parseInt(line[4])}; boolean[] visited = new boolean[F + 1]; Queue<Pair> q = new LinkedList<>(); q.add(new Pair(S, 0)); visited[S] = true; while(!q.isEmpty()) { Pair now = q.poll(); int now_floor = now.floor; int now_cnt = now.cnt; if (now_floor == G) { System.out.println(now_cnt); return; } for (int go : upDown) { int nxFloor = now_floor + go; if (nxFloor <= 0 || nxFloor > F) continue; if (visited[nxFloor]) continue; q.add(new Pair(nxFloor, now_cnt + 1)); visited[nxFloor] = true; } } System.out.println("use the stairs"); br.close(); } }

โœ๏ธ Review

  • BFS ๋ฌธ์ œ๋ผ๋Š” ๊ฒƒ์„ ์•Œ๊ณ  ํ’€์–ด์„œ ์•„์ด๋””์–ด๋Š” ๊ธˆ๋ฐฉ ์žก์•˜๋˜ ๋ฌธ์ œ์ด๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ถ„๋ฅ˜๋ฅผ ์•ˆ ๋ณด๊ณ  ์•„์ด๋””์–ด๋ฅผ ์ƒ๊ฐํ•ด๋‚ด๋Š” ์—ฐ์Šต์ด ํ•„์š”ํ•  ๊ฒƒ ๊ฐ™๋‹ค.
  • ์ €๋ฒˆ๊ณผ ๋™์ผํ•˜๊ฒŒ ๋ฐฉ๋ฌธ ์—ฌ๋ถ€๋ฅผ ์ €์žฅํ•˜๋Š” ๋ถ€๋ถ„์—์„œ์˜ ๋ฉ”๋ชจ๋ฆฌ ์ดˆ๊ณผ๋ฅผ ํ”ผํ•  ์ˆ˜ ์—†์—ˆ๋‹ค. ์ข€ ๋” ์ž์„ธํ•˜๊ฒŒ ์ƒ๊ฐํ•ด๋ณด๋Š” ์—ฐ์Šต์ด ํ•„์š”ํ•  ๊ฒƒ ๊ฐ™๋‹ค.

๐Ÿ“• ์ถœ์ฒ˜

https://www.acmicpc.net/problem/5014

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€